package leetcode12;

import java.util.ArrayDeque;
import java.util.Deque;

public class test69 {
    /**
     * 84. 柱状图中最大的矩形
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return heights[0];
        }
        int res = 0;
        int[] newHeights = new int[n + 2];
        newHeights[0] = 0;
        System.arraycopy(heights,0,newHeights,1,n);
        newHeights[n + 1] = 0;
        n += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0);

        for(int i = 1;i < n;i++){
            while(heights[i] < heights[stack.peekLast()]){
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res,curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return res;
    }
}
